package org.example;

import java.util.*;

public class Test1 {
    //自己思考，未写出来
    public List<String> ret;
    public List<String> findItinerary(List<List<String>> tickets) {
        Map<String,List<String>> map = new HashMap<>();
        for (List<String> list : tickets) {
            String start = list.get(0), end = list.get(1);
            if (map.getOrDefault(start,null) == null) {
                List<String> tmp = new ArrayList<>();
                tmp.add(end);
                map.put(start,tmp);
            }else {
                map.get(start).add(end);
                map.get(start).sort(new Comparator<String>() {
                    @Override
                    public int compare(String o1,String o2) {
                        return o1.compareTo(o2);
                    }
                });
            }
        }
        String tmp = "JFK";
        List<String> ret = new ArrayList<>();
        ret.add(tmp);
        Map<String,String> vis = new HashMap<>();
        while (true) {
            List<String> list = map.get(tmp);
            if (list == null) return ret;
            boolean flg = false;
            for (String s : list) {
                if (vis.getOrDefault(tmp,null) == null
                        || !vis.get(tmp).equals(s)) {
                    ret.add(s);
                    vis.put(tmp,s);
                    tmp = s;
                    flg = true;
                    break;
                }
            }
            if (!flg) return ret;
        }
    }

    /**
     * 方法二，超时，剩一个样例没过
     */
    boolean[] vis;
    public int size;
    public List<String> findItinerary1(List<List<String>> tickets) {
        Collections.sort(tickets, (a, b) -> a.get(1).compareTo(b.get(1)));
        ret = new ArrayList<>();
        ret.add("JFK");
        size = tickets.size();
        vis = new boolean[tickets.size()];
        backtracking(tickets);
        return ret;
    }

    public boolean backtracking(List<List<String>> tickets) {
        if (ret.size() == size + 1) {
            return true;
        }
        for (int i = 0; i < size; i++) {
            List<String> list = tickets.get(i);
            if (!vis[i] && list.get(0).equals(ret.get(ret.size() - 1))) {
                ret.add(list.get(1));
                vis[i] = true;
                if (backtracking(tickets)) {
                    return true;
                }
                ret.remove(ret.size() - 1);
                vis[i] = false;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Test1 test1 = new Test1();
        List<List<String>> lists = new ArrayList<>();
        List<String> list1 = new ArrayList<>();
        List<String> list2 = new ArrayList<>();
        List<String> list3 = new ArrayList<>();
        List<String> list4 = new ArrayList<>();
        List<String> list5 = new ArrayList<>();
//        list1.add("JFK");
//        list1.add("SFO");
//        list2.add("JFK");
//        list2.add("ALT");
//        list3.add("SFO");
//        list3.add("ALT");
//        list4.add("ALT");
//        list4.add("JFK");
//        list5.add("ALT");
//        list5.add("SFO");
        list1.add("MUC");
        list1.add("LHR");
        list2.add("JFK");
        list2.add("MUC");
        list3.add("SFO");
        list3.add("SJC");
        list4.add("LHR");
        list4.add("SFO");
        lists.add(list1);
        lists.add(list2);
        lists.add(list3);
        lists.add(list4);
        List<String> ret = test1.findItinerary(lists);
        System.out.println(666);
    }
}
